#include<stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <iostream>

/**
对长度为n的顺序表L，编写一个时间复杂度为O(n)、空间复杂度O(1)的算法，该算法删除线性表中所有值为x的数据元素
**/

#define MAXSIZE 10
typedef int ElemType;  // 定义元素类型
typedef struct
{
   ElemType data[MAXSIZE];  // 定义表长度
   int length; // 当前长度
}SqList;

// 初始化
bool InitList(SqList &L){
    for(int i=0;i<MAXSIZE; i++) L.data[i]=0;
    L.length=0;
    return true;
}

// 插入
bool ListInsert(SqList &L, ElemType e, int loc){
    // 判断位置有效范围
    if (loc < 1 || loc > L.length+1) return false;
    // 判断空间是否溢出
    if (L.length >= MAXSIZE) return false;
    // 这个是元素往后移
    for(int i=L.length; i >= loc; i--)
        L.data[i] = L.data[i-1];
    L.data[loc-1] = e;
    L.length += 1;
    return true;
}

// O(n^2)
bool solution(SqList &L, ElemType e){
    for(int i=L.length-1; i>0; i--){
        if (L.data[i]==e){
            for(int j=i; j<L.length; j++){
                L.data[j] = L.data[j+1];
            }
        }
    }
    return true;
}

bool solution2(SqList &L, ElemType x){
    int k=0;
    for(int i=0; i<L.length; i++)
        if(L.data[i]!=x){
            L.data[k] = L.data[i];
            k++;
        }
    L.length=k;
    return true;
}

bool solution3(SqList &L, ElemType x){
    int k=0, i=0;
    while (i<L.length)
    {
        if(L.data[i]==x) k++;
        else L.data[i-k]=L.data[i];
        i++;
    }
    L.length = L.length-k;
    return true;
}



// 输出操作
void PrintList(SqList L){
    for(int i=0;i<MAXSIZE; i++){
        printf("%d;", L.data[i]);
    }
    printf("\n");
}

int main(){
    SqList L;
    ElemType e;
    InitList(L);
    ListInsert(L, 1, 1);
    ListInsert(L, 1, 1);
    ListInsert(L, 1, 1);
    ListInsert(L, -1, 1);
    ListInsert(L, 1, 1);
    ListInsert(L, 1, 1);
    ListInsert(L, -1, 1);
    ListInsert(L, 1, 1);
    ListInsert(L, 1, 1);
    PrintList(L);
    solution3(L, -1);
    PrintList(L);
    printf("\n");
    printf("min:%d", e);
    system("pause");
    return 0;
}
